package bite;

import java.util.Scanner;

/**
 * Creared with IntelliJ IDEA.
 * Description:【计算字符串的编辑距离】
 * Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插
 * 入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
 * User:yxd
 * Date:2022-05-18
 * Time:20:53
 */
public class Day23_2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.next();
        String sub = input.next();
        //状态定义F(i,j)表示从i个字符的str到j个字符的sub所需的最小转换次数
        //有三种转换方式如果两个字符相等就直接等于上一次的个数,不相等就要么转换需要一次从min((i-1,j-1),(i-1,j),(i,j-1))+1
        //赋初值第一行一次加一,第一列依次加1
        int[][] dp = new int[str.length() + 1][sub.length() + 1];
        for(int i = 0;i <= str.length();i ++){
            dp[i][0] = i;
        }
        for(int i = 0;i <= sub.length();i ++){
            dp[0][i] = i;
        }
        for(int i = 1;i <= str.length();i ++){
            for (int j = 1; j <= sub.length(); j++) {
                if(str.charAt(i - 1) == sub.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    int a = Math.min(dp[i - 1][j],dp[i][j - 1]);
                    dp[i][j] = Math.min(a,dp[i - 1][j - 1]) + 1;
                }
            }
        }
        System.out.println(dp[str.length()][sub.length()]);
    }
}
